import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{1,0,1,1};
        System.out.println(s.containsNearbyDuplicate(nums, 1));
    }

    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        /**
         * 存在重复元素Ⅱ
         * 解法1：同向双指针
         * 错误·：审题错误，并非是间距为k，而是间距小于k，故此种解法无效*/
        // 1 预处理
        int n = nums.length;

        // 2 同向双指针
        int i = 0;
        int j = k;
        while(j < n) {
            if(nums[i++] == nums[j++]) {
                return true;
            }
        }

        // 3 返回值
        return false;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        /**
         * 存在重复元素Ⅱ
         * 解法2：哈希表
         * 具体思路：
         *  使用哈希表存储已遍历区域的所有元素，哈希表结构为<值：下标>,并且若是出现重复值时仅维护最新下标
         * 总结：
         *  本质就是哈希表的一些简单应用，较为初阶。使用哈希表存储已遍历区域，如此即可以O（1）的时间复杂度查找元素*/
        // 1 预处理
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();

        // 2 哈希表维护已遍历区间
        for(int i = 0; i < n; i++) {
            if(map.containsKey(nums[i]) && i-map.get(nums[i])<=k) {
                return true;
            }
            map.put(nums[i], i);
        }

        // 3 返回值
        return false;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        /**
         * 字母异位词分组
         * 需要解决的问题：
         *  1，判断两个是否为变位词
         *      变位词排序后一致
         *  2，按照什么将其进行分组
         *      使用Map<String, String[]>,key为排序后，保证唯一*/
        // 1 预处理
        int n = strs.length;
        Map<String, List<String>> map = new HashMap<>();

        // 2 执行逻辑
        for(int i = 0; i < n; i++) {
            // -以排序后字符串为键（互为变位词排序后一致）
            String curString = demo(strs[i]);
            if(map.containsKey(curString)) {
                map.get(curString).add(strs[i]);
            } else {
                List<String> tempList = new LinkedList<>();
                tempList.add(strs[i]);
                map.put(curString, tempList);
            }
        }

        // 3 返回值
        return new LinkedList<>(map.values());
    }

    public static String demo(String s1) {
        /**
         * 将字符串排序
         * */
        char[] chars = s1.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    public static boolean demo1(String s1, String s2) {
        /**
         * 用于判断两个字符串是否为异位词*/
        // 1 预处理
        if(s1.length() != s2.length()) {
            return false;
        }
        int n = s1.length();
        int[] count = new int[26];

        // 2 计数
        for(int i = 0; i < n; i++) {
            count[s1.charAt(i)-'a'] ++;
            count[s2.charAt(i)-'a'] --;
        }

        // 3 判断
        for(int e: count) {
            if(e != 0) {
                return false;
            }
        }
        return true;
    }
}
